package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/decode-ways-ii/
 * @create 2025/8/26 14:55
 * @since JDK17
 */

import java.util.Arrays;

public class Solution03 {
    static int N = ((int) (1e9 + 7));
    static int[] dp = new int[100002];
    int f1(char[] s, int cur) {
        if (cur == s.length) {
            return 1;
        }
        if (s[cur] == '0') {
            return 0;
        }
        int ans = 0, t;
        if (s[cur] != '*') {
            ans = (ans + f1(s, cur + 1)) % N;
        } else {
            ans = (ans + 9 * f1(s, cur + 1)) % N;
        }
        if (cur + 1 < s.length) {
            if (s[cur] != '*' && s[cur + 1] != '*' && (s[cur] - '0') * 10 + s[cur + 1] - '0' <= 26) { //
                ans = (ans + f1(s, cur + 2)) % N;
            } else if (s[cur] != '*' && s[cur + 1] == '*' && s[cur] <= '2') { //
                t = s[cur] == '1' ? 9 : 6;
                ans = (ans + t * f1(s, cur + 2)) % N;
            } else if (s[cur] == '*' && s[cur + 1] == '*') {
                ans = (ans + 15 * f1(s, cur + 2)) % N;
            }
        }

        return ans;
    }

    int f2(char[] s, int cur) {
        if (cur == s.length) {
            return 1;
        }
        if (s[cur] == '0') {
            return 0;
        }
        if (dp[cur] != -1) {
            return dp[cur];
        }

        int ans = 0, t;
        if (s[cur] != '*') {
            ans = (ans + f2(s, cur + 1)) % N;
        } else {
            ans = (ans + 9 * f2(s, cur + 1)) % N;
        }
        if (cur + 1 < s.length) {
            if (s[cur] != '*' && s[cur + 1] != '*' && (s[cur] - '0') * 10 + s[cur + 1] - '0' <= 26) { //
                ans = (ans + f2(s, cur + 2)) % N;
            } else if (s[cur] != '*' && s[cur + 1] == '*') { //
                t = s[cur] == '1' ? 9 : 6;
                ans = (ans + t * f2(s, cur + 2)) % N;
            } else if (s[cur] == '*' && s[cur + 1] == '*') {
                ans = (ans + 15 * f2(s, cur + 2)) % N;
            }
        }

        return dp[cur] = ans;
    }

    public int numDecodings(String str) {
        char[] s = str.toCharArray();
        Arrays.fill(dp, 0, s.length, -1);
        return f2(s, 0);

    }
}
